package com.origin.niuke.tree;

import general_class.TreeNode;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @author yzh
 * @version 1.0
 * @date 2022/5/26 20:57
 * 判断一棵二叉树是否为搜索二叉树和
 * 算法：深度优先搜索 + 广度优先搜索
 */
public class NC60 {

    public boolean[] judgeIt (TreeNode root) {
        boolean[] ans = new boolean[2];
        ans[0] = dfs(root);
        ans[1] = bfs(root);
        return ans;
    }

    int pre = Integer.MIN_VALUE;
    boolean dfs(TreeNode root) {
        if (root == null) return true;
        if (!dfs(root.left)) return false;
        if (root.val < pre) return false;
        pre = root.val;
        return dfs(root.right);
    }

    boolean bfs(TreeNode root) {
        if (root == null) return true;
        Deque<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        boolean flag = false;
        TreeNode left = null, right = null, poll = null;
        while (!queue.isEmpty()) {
            poll = queue.poll();
            left = poll.left;
            right = poll.right;
            if (left == null && right != null) return false;
            if (flag && (left != null || right != null)) return false;
            if (left != null) queue.offer(left);
            if (right != null) queue.offer(right);
            // 判断是否已经出现过节点 left = null && right != null 或者叶子节点
            if (left == null || right == null) flag = true;
        }
        return true;
    }

}
